#include<bits/stdc++.h>
using namespace std;
const int N=6e5+5;
template<typename T>inline void read(T &x){
	x=0;int f=1;char c=getchar();
	while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar(); 
	x*=f;
}
int head[N],to[N<<1],nxt[N<<1],w[N<<1],tot;
inline void add(int x,int y,int z){
	to[++tot]=y;
	nxt[tot]=head[x];
	w[tot]=z;
	head[x]=tot;
}
int T,n,m,p[N],idx,u[N],v[N],val[N];
int g[N];
long long ans;
struct BCJ{
	int f[N];
	int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
}F,L,R;
int cnt;
inline void merge(int x,int y,int z){
	if(x>y) swap(x,y);
	
	if(F.find(x)==F.find(y)) return;
	--cnt,ans+=z;
	if(R.find(x)+1==L.find(y)){
		int mid=R.f[x];
		R.f[mid]=R.f[mid+1];
		L.f[mid+1]=L.f[mid];
	}
	F.f[F.find(x)]=F.find(y);
}
int vis[N],ti;
inline int findL(int x,int l){
	int k=F.find(x),i=x;
	for(;i>=l;--i){
		if(F.find(i)==k) i=L.find(i);
		else if(vis[i]!=ti) break;
	}
	return i;
}
inline int findR(int x,int r){
	int k=F.find(x),i=x;
	for(;i<=r;++i){
		if(F.find(i)==k) i=R.find(i);
		else if(vis[i]!=ti) break;
	}
	return i;
}
int a[N],c[N];
inline void sol(int l,int r){
	ti=0;
	for(int i=l;i<=r;++i) F.f[i]=L.f[i]=R.f[i]=i,vis[i]=0;
	cnt=r-l+1;
	while(cnt>1){
		for(int i=l;i<=r;++i){
			a[i]=-1;
			c[i]=2e9;
		}
		for(int i=l;i<=r;++i){
			++ti;
			int fd=F.find(i);
			for(int o=head[i];o;o=nxt[o]){
				vis[to[o]]=ti;
				if(w[o]<c[fd]&&F.find(to[o])!=fd){
					c[fd]=w[o],a[fd]=to[o];
				}
			}
			int lt=findL(i,l),rt=findR(i,r);
			if(lt>=l&&i-lt<c[fd]) a[fd]=lt,c[fd]=i-lt;
			if(rt<=r&&rt-i<c[fd]) a[fd]=rt,c[fd]=rt-i;
			
		}
		for(int i=l;i<=r;++i){
			if(~a[i]) merge(a[i],i,c[i]);
		}
	}
}
int main(){
	freopen("up.in","r",stdin);
	freopen("up.out","w",stdout);
	read(T);
	while(T--){
		read(n),read(m);
		for(int i=1;i<=m;++i){
			read(u[i]),read(v[i]),read(val[i]);
			p[++idx]=u[i],p[++idx]=v[i];
			if(u[i]>1) p[++idx]=u[i]-1;
			if(u[i]<n) p[++idx]=u[i]+1;
			if(v[i]>1) p[++idx]=v[i]-1;
			if(v[i]<n) p[++idx]=v[i]+1;
		}
		sort(p+1,p+idx+1);
		idx=unique(p+1,p+idx+1)-p-1;
		for(int i=1;i<=idx;++i){
			int j=i;
			g[i]=i;
			while(j<idx&&p[j+1]==p[j]+1) g[++j]=i;
			i=j;
		}
		int cnt=0;
		for(int i=1;i<=m;++i){
			u[i]=lower_bound(p+1,p+idx+1,u[i])-p;
			v[i]=lower_bound(p+1,p+idx+1,v[i])-p;
			if(g[u[i]]==g[v[i]]) add(u[i],v[i],val[i]),add(v[i],u[i],val[i]);
		}
		for(int i=1;i<=idx;++i){
			if(i>1) ans+=p[i]-p[i-1];
			int j=i;
			while(j<idx&&p[j+1]==p[j]+1) ++j;
			sol(i,j);
			i=j;
		}
		if(!idx) ans=n-1;
		else ans+=n-p[idx]+p[1]-1;
		printf("%lld\n",ans);
		for(int i=0;i<=idx;++i) head[i]=vis[i]=0;
		ans=0;idx=0;tot=0;
	}
	return 0;
}

